package hwFour1;

import edu.princeton.cs.algs4.Bag;

import java.util.Scanner;

// 作业 4.1.4 4.1.5
public class Graph {

    private final int V;          // 顶点数
    private int E;                // 边数
    private Bag<Integer>[] adj;   // 邻接表

    // 构造函数（初始化图）
    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new Bag<Integer>();
        }
    }
    public Graph(Scanner in) {
        this(in.nextInt()); // 读取顶点数
        int E = in.nextInt(); // 读取边数
        for (int i = 0; i < E; i++) {
            int v = in.nextInt();
            int w = in.nextInt();
            addEdge(v, w);
        }
    }


    // 返回顶点数
    public int V() {
        return V;
    }

    // 返回边数
    public int E() {
        return E;
    }

    // 添加边 v-w
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }

    // 返回顶点 v 的邻接表
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

    // 检查是否含有边 v-w
    public boolean hasEdge(int v, int w) {
        for (int neighbor : adj[v]) {
            if (neighbor == w) {
                return true; // 如果 w 是 v 的邻居，说明存在边 v-w
            }
        }
        return false; // 如果遍历结束没有找到，说明不存在边 v-w
    }

    // 打印图信息（可选，调试用）
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " vertices, " + E + " edges\n");
        for (int v = 0; v < V; v++) {
            s.append(v + ": ");
            for (int w : this.adj(v)) {
                s.append(w + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }

    // 测试代码
    public static void main(String[] args) {
        Graph graph = new Graph(5); // 创建一个含有 5 个顶点的图

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(0, 3);
        graph.addEdge(1, 2);
        graph.addEdge(3, 4);

        System.out.println(graph);

        System.out.println("Edge 0-1: " + graph.hasEdge(0, 1)); // true
        System.out.println("Edge 0-4: " + graph.hasEdge(0, 3)); // false
        System.out.println("Edge 3-4: " + graph.hasEdge(3, 4)); // true
    }
}
